|
In computational group theory, a black box group (black-box group) is a group ''G'' whose elements are encoded by bit strings of length ''N'', and group operations are performed by an oracle (the "black box"). These operations include: • taking a product ''g''·''h'' of elements ''g'' and ''h'', • taking an inverse ''g''−1 of element ''g'', • deciding whether ''g'' = 1. This class is defined to include both the permutation groups and the matrix groups. The upper bound on the order of ''G'' given by |''G''| ≤ 2''N'' shows that ''G'' is finite. == Applications == The black box groups were introduced by Babai and Szemerédi in 1984. They were used as a formalism for (constructive) ''group recognition'' and ''property testing''. Notable algorithms include the ''Babai's algorithm'' for finding random group elements,〔L. Babai, (Local expansion of vertex-transitive graphs and random generation in finite groups ), ''Proc. 23rd STOC'' (1991), 164–174.〕 the ''Product Replacement Algorithm'',〔 〕 and ''testing group commutativity''.〔 〕 Many early algorithms in CGT, such as the Schreier–Sims algorithm, require a permutation representation of a group and thus are not black box. Many other algorithms require finding ''element orders''. Since there are efficient ways of finding the order of an element in a permutation group or in a matrix group (a method for the latter is described by Celler and Leedham-Green in 1997), a common recourse is to assume that the black box group is equipped with a further oracle for determining element orders.〔See Hоlt et al. (2005).〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Black box group」の詳細全文を読む スポンサード リンク
|